package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript:  NC105 二分查找-II
 * 请实现有重复数字的升序数组的二分查找
 * 给定一个 元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的第一个出现的target，
 * 如果目标值存在返回下标，否则返回 -1
 * @date: 2021/7/1 0:48
 * @version: 1.0
 */
public class Q78_TwoBiSearch {

    public static void main(String[] args) {
        int[] num={1,2,4,4,5}; //升序
        int target=4;
        Q78_TwoBiSearch twoBiSearch=new Q78_TwoBiSearch();
        System.out.println(twoBiSearch.search(num,target));
    }

    public int search(int[] nums,int target){
        //fixme 给定一个 元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的第一个出现的target
        //fixme 如果目标值存在返回下标，否则返回 -1
        int l=0;int r=nums.length-1;
        int mid=(l+r)/2;
        while (l<=r){ //fixme
            if (nums[mid]>nums[l]){
                l++;
            }else if (nums[mid]<nums[l]){
                r--;
            }else {
                while ((l<mid) && (nums[mid-1]==nums[mid])){ //fixme,mid >l
                    mid--;
                }
                return mid;
            }
            mid=(l+r)/2;
        }
        return -1;
    }
}
